package Sort;

/**
 * @Author: ylc
 * @Description:归并排序
 * @Date Created in 2022-06-01 16:12
 */
public class MergeSort {
    public static void mergeSort(int[] array) {
        mergeSortInternal(array, 0, array.length - 1);
    }
    // 待排序区间为 [low, high)
    private static void mergeSortInternal(int[] array, int L, int R) {
        if (L >= R) {
            return;
        }

        int mid = L + ((R - L) >> 1);

        mergeSortInternal(array, L, mid);
        mergeSortInternal(array, mid + 1, R);
        merge(array, L, mid, R);
    }
    private static void merge(int[] array, int L, int mid, int R) {
        int i = L;
        int j = mid + 1;
        int[] extra = new int[R - L + 1];
        int k = 0;

        // 选择小的放入 extra
        while (i <= mid && j <= R) {
            // 加入等于，保证稳定性
            extra[k++] = array[i] <= array[j] ? array[i++] : array[j++];
        }

        // 将左边剩余元素放入 extra
        while (i <= mid) {
            extra[k++] = array[i++];
        }
        // 将右边剩余元素放入 extra
        while (j <= R) {
            extra[k++] = array[j++];
        }

        // 从 extra 搬移回 array
        for (int t = 0; t < extra.length; t++) {
            // 需要搬移回原位置，从 L 开始
            array[L + t] = extra[t];
        }
    }

}
